/**
 *  @file DivideLink.c
 *  @desc 将一个双向链表按照结点的逻辑位置进行划分：奇数位置的结点保留在原链表中，偶数位置的结点移到新链表中
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-22 16:14
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// ------------------------- 结构体定义 -------------------------

/**
 * @brief 双向链表结点结构体定义
 */
typedef struct node {
    int data;               ///< 数据域
    struct node *next;      ///< 指向下一个结点
    struct node *pre;       ///< 指向上一个结点
} node, *link;

// ------------------------- 基础操作函数 -------------------------

/**
 * @brief 创建一个新结点
 * @param value 要存储的数据
 * @return 成功返回新结点指针，失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;

    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = value;

    return newNode;
}

/**
 * @brief 初始化链表（带头结点）
 * @param head 头结点指针的指针
 */
void initNode(link *head) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return;

    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = 0; // 头结点的数据域一般不使用
    *head = newNode;
}

// ------------------------- 插入操作函数 -------------------------

/**
 * @brief 使用头插法插入结点
 * @param head 头结点指针
 * @param value 要插入的数据
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = head->next;
    newNode->pre  = head;

    if (head->next != NULL) {
        head->next->pre = newNode;
    }
    head->next = newNode;
}

/**
 * @brief 使用尾插法插入结点
 * @param head 头结点指针
 * @param value 要插入的数据
 */
void istTail(link head, int value) {
    link cur = head;

    // 遍历到链表末尾
    while (cur->next != NULL) {
        cur = cur->next;
    }

    link newNode = createNode(value);
    if (newNode == NULL) return;

    cur->next = newNode;
    newNode->pre = cur;
}

// ------------------------- 打印链表 -------------------------

/**
 * @brief 打印链表中所有结点的数据（跳过头结点）
 * @param head 链表头指针
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;

    link cur = head->next;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// ------------------------- 删除操作函数 -------------------------

/**
 * @brief 删除链表中指定位置的结点（从位置 1 开始计数）
 * @param head 链表头指针
 * @param pos 要删除的位置
 */
void delByPos(link head, int pos) {
    if (head == NULL || head->next == NULL) return;

    int idx = 1;
    link cur = head->next;

    while (cur != NULL && idx < pos) {
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return;

    if (cur->pre != NULL) {
        cur->pre->next = cur->next;
    }
    if (cur->next != NULL) {
        cur->next->pre = cur->pre;
    }

    free(cur);
}

/**
 * @brief 在链表指定位置前插入一个新结点（位置从 1 开始）
 * @param head 链表头指针
 * @param value 要插入的值
 * @param pos 插入位置
 */
void insertByPos(link head, int value, int pos) {
    if (head == NULL || pos < 1) return;

    link cur = head;
    int idx = 0;
    while (cur != NULL && idx < pos - 1) {
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return;

    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = cur->next;
    newNode->pre = cur;

    if (cur->next != NULL) {
        cur->next->pre = newNode;
    }
    cur->next = newNode;
}

// ------------------------- 分离操作函数 -------------------------

/**
 * @brief 将链表 head 中的结点按位置奇偶分开：
 *        奇数位置结点保留在 head 中，偶数位置结点转移到 evenHead 中
 * @param head 原始链表头结点
 * @param evenHead 存放偶数位置结点的新链表头
 */
void divideLink(link head, link evenHead) {
    if (head == NULL || head->next == NULL) return;

    link cur = head->next;        // 当前节点（跳过头结点）
    link oddTail = head;          // 奇数结点尾指针
    link evenTail = evenHead;     // 偶数结点尾指针
    int idx = 1;                  // 逻辑位置，从 1 开始

    while (cur != NULL) {
        link temp = cur->next; // 先保存当前结点的下一个指针
        if (idx & 1) {
            // 奇数位置：放入原链表
            oddTail->next = cur;
            cur->pre = oddTail;
            oddTail = cur;
        } else {
            // 偶数位置：放入 evenHead 链表
            evenTail->next = cur;
            cur->pre = evenTail;
            evenTail = cur;
        }
        cur = temp;
        idx++;
    }

    // 将两个链表的尾部指针设为 NULL
    if (oddTail != NULL) {
        oddTail->next = NULL;
    }
    if (evenTail != NULL) {
        evenTail->next = NULL;
    }
}

// ------------------------- 主函数（测试用例） -------------------------

int main() {
    link head = NULL;
    initNode(&head);

    // 构造链表：1 -> 2 -> 3
    istTail(head, 1);
    istTail(head, 2);
    istTail(head, 3);

    // 初始化 even 链表（偶数位）
    link evenHead = NULL;
    initNode(&evenHead);

    // 分离奇偶位置结点
    devideLink(head, evenHead);

    // 打印两个链表
    printf("奇数位链表：\n");
    printList(head);

    printf("偶数位链表：\n");
    printList(evenHead);

    return 0;
}
